﻿/********************************************************************************
** project   ： #PROJECTNAME#
** date      ： #CREATIONDATE#
** auth      ： #AUTHORNAME#
** desc      ： 
**
** Version   ： #VERSION#
*********************************************************************************/
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// FindPath：
/// </summary>
public class FindPath : MonoBehaviour
{

    public Transform player;
    public Transform target;
    private Grid _grid;
    /// <summary>
    /// 开始
    /// </summary>
    void Start()
    {
        _grid = GetComponent<Grid>();
    }

    float currentTime = 0;
    /// <summary>
    /// 更新
    /// </summary>
    void Update()
    {
        //currentTime += Time.deltaTime;
        //if (currentTime < 0.5f)
        //    return;
        //currentTime = 0;
        FindingPath(player.position, target.position);
    }
    /// <summary>
    /// 二叉堆 添加元素后重新排序
    /// </summary>
    /// <param name="open"></param>
    private void addPointResize(List<Node> open)
    {
        int last = open.Count - 1;
        while (last > 1)
        {
            int half = last >> 1;
            if (open[last].fCost >= open[half].fCost)
            {
                break;
            }
            Node temp = open[last];
            open[last] = open[half];
            open[half] = temp;
            last >>= 1;
        }

    }
    /// <summary>
    /// 二叉堆 删除第一个元素
    /// </summary>
    /// <param name="open"></param>
    private void removePointResize(List<Node> open)
    {
        int last = open.Count - 1;
        open[1] = open[last];
        open.RemoveAt(last);
        last = open.Count - 1;
        int head = 1;
        while ((head << 1) + 1 <= last)
        {
            int child1 = head << 1;
            int child2 = child1 + 1;
            int childMin = open[child1].fCost < open[child2].fCost ? child1 : child2;
            if (open[head].fCost <= open[childMin].fCost)
            {
                break;
            }
            Node temp = open[head];
            open[head] = open[childMin];
            open[childMin] = temp;
            head = childMin;
        }
    }
    private Node nullNode = new Node(false, Vector3.zero, 1, 1);
    void FindingPath(Vector3 StartPos, Vector3 EndPos)
    {
        Node startNode = _grid.GetFromPostion(StartPos);
        Node endNode = _grid.GetFromPostion(EndPos);
        if (!startNode._canWalk || !endNode._canWalk)
            return;
        List<Node> openList = new List<Node>();
        List<Node> closeList = new List<Node>();
        openList.Add(nullNode);//二叉堆是从第一个元素开始，所以放一个空元素
        openList.Add(startNode);
        startNode.IsOpen = true;
        while (openList.Count > 1)
        {
            Node CurrentNode = openList[1];
            removePointResize(openList);
            CurrentNode.IsOpen = false;
            closeList.Add(CurrentNode);
            CurrentNode.IsClose = true;
            if (CurrentNode == endNode)
            {
                GeneratePath(startNode, endNode);
                ResetNode(openList);
                ResetNode(closeList);
                return;
            }
            List<Node> nearList = _grid.GetNearNode(CurrentNode);
            int count = nearList.Count;
            for (int i = 0; i < count; i++)
            {
                var node = nearList[i];
                if (!node._canWalk || node.IsClose)
                    continue;
                int newCost = CurrentNode.gCost + GetDistanceNodes(CurrentNode, node);
                if (newCost < node.gCost || !node.IsOpen)
                {
                    node.gCost = newCost;
                    node.hCost = GetDistanceNodes(node, endNode);
                    node.parent = CurrentNode;
                    if (!node.IsOpen)
                    {
                        openList.Add(node);
                        node.IsOpen = true;
                        addPointResize(openList);
                    }
                }
            }
        }
        ResetNode(openList);
        ResetNode(closeList);
    }
    private void ResetNode(List<Node> list)
    {
        int count = list.Count;
        for (int i = 0; i < count; i++)
        {
            list[i].IsClose = false;
            list[i].IsOpen = false;
        }
    }
    public void GeneratePath(Node startNode, Node endNode)
    {
        List<Node> path = new List<Node>();
        Node temp = endNode;
        while (temp != startNode)
        {
            path.Add(temp);
            temp = temp.parent;
        }
        path.Reverse();
        _grid.path = path;
    }
    public int GetDistanceNodes(Node a, Node b)
    {
        int cntX = Mathf.Abs(a._gridX - b._gridX);
        int cntY = Mathf.Abs(a._gridY - b._gridY);
        if (cntX > cntY)
        {
            return 14 * cntY + 10 * (cntX - cntY);
        }
        else
        {
            return 14 * cntX + 10 * (cntY - cntX);
        }
    }
}
